
//请使用课堂上讲的各个排序算法
// 给你一个整数数组 nums，请你将该数组升序排列。
class Solution {
    /**
     * 计数排序
     * 执行用时：3 ms
     * 内存消耗：50.7 MB
     * @param nums
     * @return
     */
    public static int [] sortArray(int[] nums) {
        //找数组中的最大值和最小值
    int min=nums[0];
    int max=nums[0];
        for (int i = 0; i <nums.length ; i++) {
        if(nums[i]<min){
            min=nums[i];
        }
        if(nums[i]>max){
            max=nums[i];
        }
    }
    //开辟一个数组
    int len=max-min+1;
    int [] tmp=new int[len];
        for (int i = 0; i <nums.length ; i++) {
        int val=nums[i];
        tmp[val-min]++;
    }
    int index=0;
        for(int i=0;i< tmp.length;i++){
        while(tmp[i]>0){
            nums[index]=i+min;
            tmp[i]--;
            index++;
        }
    }
        return nums;
}


/**
 * 归并排序
 * 执行用时：30 ms
 * 内存消耗：50.4 MB
 * @param nums
 */
    public static void sortArray7(int[] nums) {
        //分组
        int end=nums.length;
        mergeSort(nums,0,end-1);
    }
    protected static void mergeSort(int [] arr,int start,int end){
        if(start>=end){
            return;
        }
        int mid=(start+end)/2;
        mergeSort(arr, start, mid);
        mergeSort(arr,mid+1,end);
        //合并
        merge(arr,start,mid,end);
    }
    protected  static void merge(int [] arr,int start,int mid,int end){
        int s1=start;
        int e1=mid;
        int s2=mid+1;
        int e2=end;
        int [] arr1=new int[end-start+1];
        int count=0;
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                arr1[count++]=arr[s1++];
            }else{
                arr1[count++]=arr[s2++];
            }
        }
        while(s1<=e1){
            arr1[count++]=arr[s1++];
        }
        while(s2<=e2){
            arr1[count++]=arr[s2++];
        }
        //将arr1的值赋值回
        for (int i = 0; i <count ; i++) {
            arr[i+start]=arr1[i];
        }
    }
        /**
         * 堆排序
         * 执行用时：30 ms
         * 内存消耗：51.4 MB
         * @param nums
         */
    public static void sortArray6(int[] nums) {
        //升序，建大堆
        createHeap(nums);
        //出堆
        int end=nums.length-1;
        while(end>0){
            swap(nums, 0, end);
            shiftDown(nums, 0, end);
            end--;
        }
    }
    protected static void createHeap(int [] nums){
        int parent=(nums.length-1-1)/2;
        int len= nums.length;
        for (int i = parent; i >=0; i--) {
            //向下调整
            shiftDown(nums, i,len);
        }
    }
    protected static void shiftDown(int [] nums,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&nums[child+1]>nums[child]){
                child++;
            }
            if(nums[child]>nums[parent]){
                swap(nums,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

        /**
         * 希尔排序
         * 超时延迟
         * @param nums
         */
    public static void  sortArray5(int[] nums) {
        int gap=nums.length-1;
        while(gap> 1) {
            gap=gap/2;
            for (int i =gap; i < nums.length; i++) {
                int tmp = nums[i];
                int j = i - gap;
                for (; j >= 0; j=j-gap) {
                    if (nums[j] >tmp) {
                        nums[j + gap] = nums[j];
                    } else {
                        break;
                    }
                }
                nums[j + gap] = tmp;
            }
        }
    }

        /**
         * 快排的挖坑法
         * 执行用时：913 ms
         * 内存消耗：55.8 MB
         * @param nums
         * @return
         */
    public static void sortArray4(int[] nums) {
        quickSort(nums,0,nums.length-1);
    }
    protected static void quickSort(int[] arr,int start,int end){
        if(start>=end){
            return;
        }
        //三数取中
        int mid=FindMidIndex(arr,start,end);
        swap(arr,start,mid);
        int index=partition(arr,start,end);
        quickSort(arr,start,index-1);
        quickSort(arr,index+1,end);

    }
    private static int  FindMidIndex(int [] arr,int start,int end){
        int mid=(start+end)/2;
        if(arr[start]>arr[end]){
            if(arr[mid]>arr[start]){
                return start;
            }else if(arr[mid]<arr[end]){
                return end;
            }else{
                return  mid;
            }
        }else{
            if(arr[mid]>arr[end]){
                return end;
            }else if(arr[mid]<arr[start]){
                return start;
            }else {
                return mid;
            }
        }
    }
    private static int partition(int [] arr,int left,int right){
        int tmp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=tmp){
                right--;
            }
             arr[left]=arr[right];
            while(left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;
        return left;
    }

        /**
         * 选择排序
         * 超出时间限制
         * @param nums
         * @return
         */
    public int[] sortArray3(int[] nums) {
        for (int i = 0; i < nums.length ; i++) {
            int tmp=i;
            for (int j = i+1; j < nums.length ; j++) {
                if(nums[j]<nums[tmp]){
                    tmp=j;
                }
            }
            swap(nums,i,tmp);
        }
        return nums;
    }
    protected static  void swap(int [] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
        /**
         * 插入排序
         * 超出时间限制
         * @param nums
         * @return
         */
    public int[] sortArray2(int[] nums) {
        for (int i = 1; i < nums.length ; i++) {
            int tmp=nums[i];
            int j=i-1;
            for (; j>=0 ; j--) {
                if(nums[j]>tmp) {
                 nums[j+1]=nums[j];
                }else{
                    break;
                }
            }
            nums[j+1]=tmp;
        }
        return nums;
    }

        /**
         * 冒泡排序
         * 超出时间限制
         * @param nums
         * @return
         */
    public int[] sortArray1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j + 1] < nums[j]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
        return nums;
    }

}